package prefixTree;

/**
 * 题目 ：最短单词编码
 * 题目详述 ：
 * 单词数组words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
 *
 * words.length == indices.length
 * 助记字符串 s 以 '#' 字符结尾
 * 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等
 * 给定一个单词数组words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
 */
public class MinimumLengthEncoding {
    /**
     *  核心思想 ：
     *  在于保留所有不是其他单词后缀的单词
     *  步骤：
     *  （1）构建前缀树，将字符串数组中的字符串进行反转之后，插入到前缀树中；
     *  （2）遍历已经构建好的前缀树，获取到每一个单词的大小 + 1，同时相互累加而获取到最终结果；
     */
    // 将totalLength变量定义为全局变量，从而来避免函数值传递的问题，
    // 值传递 ：只会在调用的函数中对于所传递的变量值进行修改，而不会对于main中变量本身的值进行修改
    int totalLength;
    public int minimumLengthEncoding(String[] words) {
        // 获取已经初始化过的前缀树
        TrieNode root = findTrieNode(words);

        // 使用深度优先遍历，获取前缀树中所有单词的长度；
        /**
         * （1）第一个参数 ：传入当前正在遍历的前缀树节点；
         * （2）第二个参数 ：当前遍历的节点到根节点之间的距离 + 1；
         * （3）第三个参数 ：前缀树中所有单词的总长度（即，最后所需要返回的结果）
         */
        // 由于记录的单词长度要比单词长度 + 1，所以通过传入长度初始值为1，来进行解决长度不一致的问题；
        totalLength = 0;
        dfs(root,1);
        return totalLength;
    }

    private void dfs(TrieNode root, int i) {
        // 标志位，用来判断是否位叶子节点；
        // 即，若是当前节点位叶子节点的话，就需要将（当前节点到根节点的距离）累加到totalLength中；
        boolean flag = true;
        // 遍历当前的前缀树节点中的所有子节点
        for (TrieNode child : root.children) {
            // 若是当前前缀树节点的后续子节点为空的话，则代表当前遍历的节点为前缀树的叶子节点；
            if(child != null){
                // 若是当前前缀树节点不为叶子节点的话，需要将flag标志位置为false，以防止去触发累加到totalLength的操作；
                flag = false;
                dfs(child ,i + 1);
            }
        }
        // 若是标志位为true的话，说明当前正在遍历的前缀树节点是前缀树的叶子节点；
        if(flag){
            totalLength += i;
        }
    }

    public TrieNode findTrieNode(String[] words){
        TrieNode root = new TrieNode();
        // 遍历整个字符串数组
        for (String word : words) {
            TrieNode node = root;
            // 反转遍历字符串中的字符
            for(int i = word.length() - 1; i >= 0 ; i--){
                // 获取字符串中对应索引的字符
                char ch = word.charAt(i);
                // 若是当前遍历的前缀树节点的子数组，并不包含字符串中对应索引的字符的话，则需要去新增前缀树节点
                if(node.children[ch - 'a'] == null){
                    node.children[ch - 'a'] = new TrieNode();
                }
                // node节点后移
                node = node.children[ch - 'a'];
            }
        }
        return root;
    }
    /**
     * 分析 ：
     * 时间复杂度：初始化前缀树的时间复杂度：O（n*m）；dfs函数的时间复杂度为O（n）（其中n，为前缀树中节点总数）；
     * ===》 总的时间复杂度：O（n*m）；
     */
}
